package com.zk.algorithm.tree;

import com.zk.algorithm.bean.TreeNode;
import com.zk.algorithm.factory.TreeFactory;

/**
 * @author zk
 */
public class IsSubTree {

    // ==============================
    // 整棵树 s 中间包含树 t
    // 树的子结构 剑指 Offer 上面的
    // ==============================

    public boolean isSubtree(TreeNode s, TreeNode t) {
        boolean res = false;

        if (s != null && t != null) {

            if (s.val == t.val) {
                res = containsSubTree(s, t);
            }

            if (!res) {
                res = containsSubTree(s.left, t);
            }

            if (!res) {
                res = containsSubTree(s.right, t);
            }

        }

        return res;
    }

    protected boolean containsSubTree(TreeNode s, TreeNode t) {
        // 找完 t 整颗树了?
        if (t == null) {
            return true;
        }

        if (s == null) {
            return false;
        }

        if (s.val != t.val) {
            return false;
        }

        return containsSubTree(s.left, t.left) && containsSubTree(s.right, t.right);
    }

    // ==============================
    // 整棵树 s 下部包含树 t，即从某个节点开始一直相同，不是 s 的中间一部分包含 t
    // LeetCode 572
    // ==============================

    public boolean isSubtree2(TreeNode s, TreeNode t) {
        if (s == null) return false;
        if (isSame(s, t)) return true;
        return isSubtree2(s.left, t) || isSubtree2(s.right, t);
    }

    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;

        if (s.val != t.val) return false;

        return isSame(s.left, t.left) && isSame(s.right, t.right);
    }

    public static void main(String...args) {
        boolean result = new IsSubTree().isSubtree(
                TreeFactory.buildTree(new int[]{ 3,4,5,1,2,Integer.MIN_VALUE,Integer.MIN_VALUE,0 }),
                TreeFactory.buildTree(new int[]{ 4,1,2 })
        );
        System.out.println(result);

        result = new IsSubTree().isSubtree(
                TreeFactory.buildTree(new int[]{ 3,4,5,1,2 }),
                TreeFactory.buildTree(new int[]{ 4,1,2 })
        );
        System.out.println(result);

        result = new IsSubTree().isSubtree(
                TreeFactory.buildTree(new Integer[]{ 1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,2 }),
                TreeFactory.buildTree(new Integer[]{ 1,null,1,null,1,null,1,null,1,null,1,2 })
        );
        System.out.println(result);
    }

}
